Cryptography provides methods of providing privacy and authenticity for remote communications and data storage. Privacy is achieved by encryption of data, usually using the techniques of symmetric cryptography (so called because the same mathematical key is used to encrypt and decrypt the data). Authenticity is achieved by the functions of user identification, data integrity, and message non-repudiation. These are best achieved via asymmetric (or public-key) cryptography.
In particular, public-key cryptography enables encrypted communication between users that have not previously established a shared secret key between them. This is most often done using a combination of symmetric and asymmetric cryptography: public-key techniques are used to establish user identity and a common symmetric key, and a symmetric encryption algorithm is used for the encryption and decryption of the actual messages. The former operation is called key agreement. Prior establishment is necessary in symmetric cryptography, which uses algorithms for which the same key is used to encrypt and decrypt a message. Public-key cryptography, in contrast, is based on key pairs. A key pair consists of a private key and a public key. As the names imply, the private key is kept private by its owner, while the public key is made public (and typically associated to its owner in an authenticated manner). In asymmetric encryption, the encryption step is performed using the public key, and decryption using the private key. Thus the encrypted message can be sent along an insecure channel with the assurance that only the intended recipient can decrypt it.
The key agreement can be interactive (e.g., for encrypting a telephone conversation) or non-interactive (e.g., for electronic mail).
User identification is most easily achieved using what are called identification protocols. A related technique, that of digital signatures, provides data integrity and message non-repudiation in addition to user identification.
The public key is used for encryption or signature verification of a given message, and the private key is used for decryption or signature generation of the given message.
The use of cryptographic key pairs was disclosed in U.S. Pat. No. 4,200,770, entitled “CRYPTOGRAPHIC APPARATUS AND METHOD.” Also disclosed is the application of key pairs to the problem of key agreement over an insecure communication channel. The algorithms specified in the patent rely for their security on the difficulty of the mathematical problem of finding a discrete logarithm. U.S. Pat. No. 4,200,770 is incorporated herein in its entirety by reference.
In order to undermine the security of a discrete-logarithm based crypto algorithm, an adversary must be able to perform the inverse of modular exponentiation (i.e., a discrete logarithm). There are mathematical methods for finding a discrete logarithm (e.g., the Number Field Sieve), but these algorithms cannot be done in any reasonable time using sophisticated computers if certain conditions are met in the specification of the crypto algorithm.
In particular, it is necessary that the numbers involved be large enough. The larger the numbers used, the more time and computing power is required to find the discrete logarithm and break the cryptograph. On the other hand, very large numbers lead to very long public keys and transmissions of cryptographic data. The use of very large numbers also requires large amounts of time and computational power in order to perform the crypto algorithm. Thus, cryptographers are always looking for ways to minimize the size of the numbers involved, and the time and power required, in performing the encryption and/or authentication algorithms. The payoff for finding such a method is that cryptography can be done faster, cheaper, and in devices that do not have large amounts of computational power (e.g., hand-held smart-cards).
A discrete-logarithm based crypto algorithm can be performed in any mathematical setting in which certain algebraic rules hold true. In mathematical language, the setting must be a finite cyclic group. The choice of the group is critical in a cryptographic system. The discrete logarithm problem may be more difficult in one group than in another for which the numbers are of comparable size. The more difficult the discrete logarithm problem, the smaller the numbers that are required to implement the crypto algorithm. Working with smaller numbers is easier and faster than working with larger numbers. Using small numbers allows the cryptographic system to be higher performing (i.e., faster) and requires less storage. So, by choosing the right kind of group, a user may be able to work with smaller numbers, make a faster cryptographic system, and get the same, or better, cryptographic strength than from another cryptographic system that uses larger numbers.
1.1 Elliptic Curves & Cryptography
The groups referred to above come from a setting called finite fields. Methods of adapting discrete-logarithm based algorithms to the setting of elliptic curves are known. However, finding discrete logarithms in this kind of group is particularly difficult. Thus elliptic curve-based crypto algorithms can be implemented using much smaller numbers than in a finite-field setting of comparable cryptographic strength. Thus the use of elliptic curve cryptography is an improvement over finite-field based public-key cryptography.
In practice, an Elliptic Curve group over a finite field F is formed by choosing a pair of a and b coefficients, which are elements within F. The group consists of a finite set of points P(x,y) which satisfy the elliptic curve equationF(x,y)=y2−x3−ax−b=0  1.1
together with a point at infinity, O. It is worth noting that an elliptic curve equation contains one cubic variable termed the x-coordinate and one quadratic variable termed the y-coordinate. The coordinates of the point, x and y, are elements of F represented in N-bit strings. In what follows, a point is either written as a capital letter, e.g. P, or as a pair in terms of the affine coordinates, i.e. (x,y).
The Elliptic Curve Cryptosystem relies upon the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP) to provide its effectiveness as a cryptosystem. Using multiplicative notation, the problem can be described as: given points B and Q in the group, find a number k such that Bk=Q; where k is called the discrete logarithm of Q to the base B. Using additive notation, the problem becomes: given two points B and Q in the group, find a number k such that kB=Q.
In an Elliptic Curve Cryptosystem, the large integer k is kept private and is often referred to as the secret key. The point Q together with the base point B are made public and are referred to as the public key. The security of the system, thus, relies upon the difficulty of deriving the secret k, knowing the public points B and Q. The main factor that determines the security strength of such a system is the size of its underlying finite field. In a real cryptographic application, the underlying field is made so large that it is computationally infeasible to determine k in a straightforward way by computing all the multiples of B until Q is found.
The core of the elliptic curve geometric arithmetic is an operation called scalar multiplication which computes kB by adding together k copies of the point B. The scalar multiplication is performed through a combination of point-doubling and point-addition operations. The point-addition operation adds two distinct points together and the point-doubling operation adds two copies of a point together. To compute, for example, 11 B=(2*(2*(2B)))+2B=Q, it would take 3 point-doublings and 2 point-additions.
Addition of two points on an elliptic curve is calculated as follows. When a straight line is drawn through the two points, the straight line intersects the elliptic curve at a third point. The point symmetric to this third intersecting point with respect to the x-axis is defined as a point resulting from the addition.
Doubling a point on an elliptic curve is calculated as follows. When a tangent line is drawn at a point on an elliptic curve, the tangent line intersects the elliptic curve at another point. The point symmetric to this intersecting point with respect to the x-axis is defined as a point resulting from the doubling.
Table 1 illustrates the addition rules for adding two points (x1,y1) and (x2,y2), that is,(x3,y3)=(x1,y1)+(x2,y2)  1.2
TABLE 1Summary of Addition Rules: (x3, y3) = (x1, y1) + (x2, y2)General Equationsx3 = m2 − x2 − x1y3 = m (x3 − x1) + y1 Point Addition  m  =                    y        2            -              y        1                            x        2            -              y        1             Point Doubling (x3, y3) = 2(x1, y1)  m  =                    3        ⁢                  x          1          2                    -      α              2      ⁢              y        1             (x2, y2) = −(x1, y1)(x3, y3) = (x1, y1) + (−(x2, y2)) = O(x2, y2) = O(x3, y3) = (x1, y1) + O = (x1, y1)−(x1, y1)=(x1, −y1)1.2 Overview of Elliptic Curve Encryption and DecryptionGiven a message point (xm,ym), a base point (xB,yB), and a given key, k, the cipher point (xC,yC) is obtained using the following equation,(xC,yC)=(xm,ym)+k(xB,yB)  1.3There are two basics steps in the computation of the above equations. The first is to find the scalar multiplication of the base point with the key, “k(xB,yB)”. The resulting point is then added to the message point, (xm,ym) to obtain the cipher point.At the receiver, the message point is recovered from the cipher point which is usually transmitted, the shared key and the base point, that is(xm,ym)=(xC,yC)−k(xB,yB)  1.41.3 Embedding Message Data on Elliptic Curve Points
As indicated earlier, the x-coordinate, xm, is represented as an N-bit string. Not all of the N-bits are used to carry information about the data of the secret message.
Assuming that the number of bits of the x-coordinate, xm, that do not carry data is L. The extra bits, L, are used to ensure that message data when embedded into the x-coordinate will lead to an xm value that satisfies the elliptic curve equation, equation 1.1. Usually, if the first guess of xm is not on a curve, then the second or third try is. This was first proposed in “N. Kobltiz, Introduction to Elliptic Curve and Modular Forms, New York: Springer-Verlag 1993”.
Therefore the number of bits used to carry the bits of the message data is (N−L). Assuming that the secret data is a K-bit string. The number of elliptic curve points needed to encrypt the K-bit data is
      ⌈          K              N        -        L              ⌉    .
It is important to note that the y-coordinate, ·ym, of the message point carries no data bits.
1.4 Attacks
The difficulty in solving the elliptic curve discrete logarithm problem has been established theoretically while information associated with secret information such as the private key or the like may leak out in cryptographic processing in real mounting. Thus, there has been proposed an attack method of so-called power analysis in which the secret information is decrypted on the basis of the leak information.
An attack method in which change in voltage is measured in cryptographic processing using secret information such as DES (Data Encryption Standard) or the like, so that the process of the cryptographic processing is obtained and the secret information is inferred on the basis of the obtained process is disclosed in P. Kocher, J. Jaffe and B. Jun Differential Power Analysis, Advances in Cryptology: Proceedings of CRYPTO '99, LNCS 1666, Springer-Verlag, (1999) pp. 388-397. This attack method is called DPA (Differential Power Analysis).
An elliptic curve cryptosystem to which the above-mentioned attack method is applied is disclosed in J. Coron, Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems, Cryptographic Hardware and Embedded Systems: Proceedings of CHES '99, LNCS 1717, Springer-Verlag, (1999) pp. 292-302. In the elliptic curve cryptosystem, encryption, decryption, signature generation and signature verification of a given message have to be carried out with elliptic curve operations. Particularly, calculation of scalar multiplication on an elliptic curve is used in cryptographic processing using a scalar value as secret information.
As one of the measures against DPA attack on elliptic curve cryptosystems, a method using randomized projective coordinates is known. This is a measure against an attack method of observing whether a specific value appears or not in scalar multiplication calculation, and inferring a scalar value from the observing result. That is, by multiplication with a random value, the appearance of such a specific value is prevented from being inferred.
In the above-mentioned background-art elliptic curve cryptosystem, attack by power analysis such as DPA or the like was not taken into consideration. Therefore, to relieve the attack by power analysis, extra calculation, or the like, other than necessary calculation had to be carried out using secret information to weaken the dependence of the process of the cryptographic processing and the secret information on each other. Thus, time required for the cryptographic processing increased so that cryptographic processing efficiency was lowered particularly in a computer such as an IC card, or the like, which was slow in calculation speed, a server managing an enormous number of cryptographic processes, or the like. In addition, the dependence of cryptographic processing process and secret information on each other cannot be cut off perfectly. In addition, if priority was given to the cryptographic processing efficiency, the cryptosystem was apt to come under attack by power analysis so that there was a possibility that secret information would leak out.
1.5 Speed of Computations
With the development of information communication networks, cryptographic techniques have been indispensable elements for concealment or authentication about electronic information. Speeding up is demanded along with the security of the cryptographic techniques. The elliptic curve discrete logarithm problem is so difficult that elliptic curve cryptosystems can make key length shorter than that in RSA (Rivest-Shamir-Adleman) cryptosystems basing their security on the difficulty of factorization into prime factors. Thus, the elliptic curve cryptosystems open the way to comparatively high-speed cryptographic processing. However, the processing speed is not always high enough to satisfy smart cards which have restricted throughput or servers which have to carry out large volumes of cryptographic processing. It is therefore demanded to further speed up the processing in cryptosystems.
The two equations for m in Table 1 are called slope equations. Computation of a slope equation in finite fields requires one finite field division. Alternatively, the slope computation can be computed using one finite field inversion and one finite field multiplication. Finite field division and finite field inversion are expensive computationally because they require extensive CPU cycles for the manipulation of two elements of a finite field with a large order. Today, it is commonly accepted that a point-doubling and point-addition operation each requires one inversion, two multiplies, a square, and several additions. To date there are techniques to compute finite field division and finite field inversion, and techniques to trade expensive inversions for multiplications by performing the operations in projective coordinates.
In cases where field inversions are significantly more expensive than multiplication, it is efficient to implement projective coordinates. An elliptic curve projective point (X,Y,Z) in conventional projective (or homogeneous) coordinates satisfies the homogeneous Weierstrass equation,{tilde over (F)}(X,Y,Z)=Y2Z−X3−aXZ2−bZ3=0  1.5
and, when z≠0, it corresponds to the affine point
      (          x      ,      y        )    =            (                        X          Z                ,                  Y          Z                    )        .  It turns out that other projective representations lead to more efficient implementations of the group operation. In particular, the Jacobian representations where the triplets (X,Y,Z) corresponds to the affine coordinates
      (          x      ,      y        )    =      (                  X                  Z          2                    ,              Y                  Z          3                      )  whenever z≠0. This is equivalent to using Jacobian elliptic curve equation that is of the form,{tilde over (F)}J(X,Y,Z)=Y2−X3−aXZ4−bZ6=0  1.6
Another commonly used projection is the Chudnovsky-Jacobian coordinates.
In general terms, the relationship between the affine coordinates and the projection coordinates can be written as
      (          x      ,      y        )    =      (                  X                  Z          i                    ,              Y                  Z          j                      )  where the values of i and j depend on the choice of the projective coordinates. For example for homogeneous coordinates, i=1 and j=1.
The use of projective coordinates circumvents the need for division in the computation of each point addition and point doubling during the calculation of scalar multiplication. Therefore, finite field division can be avoided in the calculation of scalar multiplication,
  k  (                    X        B                    Z        B        i              ,                  Y        B                    Z        B        j              )when using projective coordinate.
The last addition for the computation of the cipher point,
      (                            X          C                          Z          C          i                    ,                        Y          C                          Z          C          j                      )    ,i.e. the addition of the two points
      (                            X          m                          Z          m          i                    ,                        Y          m                          Z          m          j                      )    ⁢          ⁢  and  ⁢          ⁢      k    (                            X          B                          Z          B          i                    ,                        Y          B                          Z          B          j                      )  can also be carried out in the chosen projection coordinate, that is
      (                            X          C                          Z          C          i                    ,                        Y          C                          Z          C          j                      )    =            (                                    X            m                                Z            m            i                          ,                              Y            m1                                Z            m            j                              )        +          (                                    X            B                                Z            B            i                          ,                              Y            B                                Z            B            j                              )      
It should be pointed out that Zm=1.
However, one division (or one inversion and one multiplication) must still be carried out to calculate
            x      C        =                  X        C                    Z        C        i              ,since only the affine x-coordinate of the cipher point, xC, is sent by the sender.
Therefore the encryption of (N−L) bits of the secret message using elliptic curve encryption requires at least one division when using projective coordinates. Similarly, the decryption of a single message encrypted using elliptic curve cryptography also requires at least one division when using projective coordinates.
The state of elliptic curve cryptography is described in a paper by Neal Koblitz, Alfred Meneges and Scott Vanstone, Design, Codes and Cryptography 19 173-193 (2000) which is incorporated herein in its entirety by reference. More recent developments are described in the Vanstone et al. U.S. Pat. No. 6,424,712 and the published patent applications U.S. 2003/0059042 of Okeya et al., No. 2003/0123656 of Izu et al. and 2003/0142820 of Futa et al. all of which are incorporated herein by reference. An earlier U.S. Pat. No. 4,200,770 of Hellman et al. discloses an earlier cryptographic apparatus and method and is also incorporated herein by reference.
The 0059042, 0123656 and 0142820 patent applications and U.S. Pat. No. 6,424,712 address the issue of speeding up elliptic curve scale multiplications.